package com.qcby.demo;

import java.util.Stack;

/**
 * 用 双栈 实现一个队列
 * 基本思路：通过两个栈来模拟一个队列的先进先出（FIFO）特性
 * 具体的实现方法：利用一栈来处理入队操作，另一栈来处理出队操作。
 */
public class QueueUsingTwoStacks<T> {  // QueueUsingTwoStacks<T>，是一个通用队列类，支持任何类型的元素
    private Stack<T> stack1; // 主栈用于入队
    private Stack<T> stack2; // 辅助栈用于出队

    /**
     * 构造函数的主要作用是
     * 确保每次创建 QueueUsingTwoStacks 类的新实例时，
     * stack1 和 stack2 都会被正确地初始化为新的栈对象。
     *  这是确保队列操作能够正常进行的前提，
     *  因为没有这两个栈，队列的基本功能将无法实现。
     */
    // 构造函数。公有的构造函数，可以在任何其他类中访问。
    public QueueUsingTwoStacks() {
        stack1 = new Stack<>();  // 创建了一个新的 Stack 对象并将其赋值给 stack1
        stack2 = new Stack<>();  // 初始化辅助栈 stack2
    }

    // 入队操作
    public void enqueue(T item) {
        stack1.push(item);
    }

    // 出队操作
    public T dequeue() {
        if (stack2.isEmpty()) {
            while (!stack1.isEmpty()) {
                stack2.push(stack1.pop());
            }
        }
        if (stack2.isEmpty()) {
            throw new IllegalStateException("Queue is empty");
        }
        return stack2.pop();
    }

    // 查看队头元素
    public T peek() {
        if (stack2.isEmpty()) {
            while (!stack1.isEmpty()) {
                stack2.push(stack1.pop());
            }
        }
        if (stack2.isEmpty()) {
            throw new IllegalStateException("Queue is empty");
        }
        return stack2.peek();
    }

    // 检查队列是否为空
    public boolean isEmpty() {
        return stack1.isEmpty() && stack2.isEmpty();
    }

    // 获取队列的大小
    public int size() {
        return stack1.size() + stack2.size();
    }

    public static void main(String[] args) {
        QueueUsingTwoStacks<Integer> queue = new QueueUsingTwoStacks<>();

        queue.enqueue(1);
        queue.enqueue(2);
        queue.enqueue(3);

        System.out.println("队列的头元素是: " + queue.peek()); // 输出头元素 1
        System.out.println("出队元素: " + queue.dequeue()); // 输出出队 1
        System.out.println("队列的头元素是: " + queue.peek()); // 输出头元素 2
        System.out.println("出队元素: " + queue.dequeue()); // 输出出队 2
        System.out.println("队列的头元素是: " + queue.peek()); // 输出头元素 3
        System.out.println("出队元素: " + queue.dequeue()); // 输出出队 3

        // 检查队列是否为空
        System.out.println("队列是否为空: " + queue.isEmpty()); // 输出 true
    }
}
